package m202406.d25;

import java.util.PriorityQueue;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/6/25 22:32
 */
public class LCR078 {

    public static void main(String[] args) {
        ListNode l1 = build(new int[]{-8, -7, -7, -5, 1, 1, 3, 4});
        ListNode l2 = build(new int[]{-2});
        ListNode l3 = build(new int[]{-10, -10, -7, 0, 1, 3});
        ListNode l4 = build(new int[]{2});
        LCR078 lcr078 = new LCR078();
        ListNode listNode = lcr078.mergeKLists(new ListNode[]{l1, l2, l3});
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    private static ListNode build(int[] ints) {
        ListNode l = new ListNode();
        ListNode p = l;
        for (int i : ints) {
            p.next = new ListNode(i);
            p = p.next;
        }
        return l.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
//        Heap heap = new Heap(lists.length);
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            if (list == null) {
                continue;
            }
            heap.add(list);
        }

        ListNode res = new ListNode(-1);
        ListNode p = res;

        for (ListNode node = heap.poll(); node != null; node = heap.poll()) {
            p.next = node;
            p = p.next;
            if (node.next == null) {
                continue;
            }
            heap.add(node.next);
        }
        return res.next;
    }

    private static class Heap {
        ListNode[] data;

        private int size;

        private Heap(int size) {
            this.data = new ListNode[size + 1];
            this.size = 0;
        }

        public void add(ListNode node) {
            if (node == null) {
                return;
            }
            int index = size + 1;
            this.data[index] = node;
            int parent = parent(index);
            while (parent >= 1 &&
                    this.data[parent].val > this.data[index].val) {
                ListNode temp = this.data[parent];
                this.data[parent] = this.data[index];
                this.data[index] = temp;
                index = parent;
                parent = parent(index);
            }
            size++;
        }

        public ListNode get() {
            if (size < 1) {
                return null;
            }
            ListNode res = this.data[1];
            if (size == 1) {
                size--;
                this.data[1] = null;
                return res;
            }
            ListNode last = this.data[size];
            this.data[size] = null;
            size--;
            this.data[1] = last;
            int p = 1;
            int left = left(p);
            int right = right(p);

            if ((right >= this.data.length || this.data[right] == null)
                    && left < this.data.length && this.data[left] != null && this.data[left].val < this.data[p].val) {
                ListNode temp = this.data[p];
                this.data[p] = this.data[left];
                this.data[left] = temp;
                return res;
            }

            while (right < this.data.length && this.data[right] != null) {

                if (this.data[p].val < this.data[left].val
                        && this.data[p].val < this.data[right].val) {
                    break;
                }
                if (this.data[left].val < this.data[right].val) {
                    ListNode temp = this.data[p];
                    this.data[p] = this.data[left];
                    this.data[left] = temp;
                    p = left;
                } else {
                    ListNode temp = this.data[p];
                    this.data[p] = this.data[right];
                    this.data[right] = temp;
                    p = right;
                }
                left = left(p);
                right = right(p);
            }
            return res;
        }

        public int parent(int i) {
            return i >> 1;
        }

        public int left(int i) {
            return i << 1;
        }

        public int right(int i) {
            return (i << 1) + 1;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
